package com.example.tencentTrain;


/**
 * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
 *
 *  示例 1:
 *  输入: num1 = "2", num2 = "3"
 * 输出: "6"
 *
 *  示例 2:
 *  输入: num1 = "123", num2 = "456"
 * 输出: "56088"
 */
public class Leetcode43_Multiply {
    public static void main(String[] args) {
        String num1 = "123";
        String num2 = "456";
        System.out.println(new Solution().multiply(num1, num2));
//        System.out.println((3 * 6 + 1) / 10);// carry
//        System.out.println((3 * 6 + 1) % 10);// sum
//        System.out.println(new StringBuilder().append(1).append(2).toString());
    }

    static class Solution {
        /**
         * 两个数相乘结果最多为一个 m + n + 1 位数
         *
         * 对于任意 0<= i <len1 和 0 <= j< n，
         * num1[i] × num2[j] 的结果位于 resArr[i+j+1]，
         * 如果 resArr[i+j+1] >=10，则将进位部分加到 ansArr[i+j]。
         * @param num1
         * @param num2
         * @return
         */
        private String multiply2(String num1, String num2) {
            char[] chars1 = num1.toCharArray();
            char[] chars2 = num2.toCharArray();
            if (chars1[0] == '0' || chars2[0] == '0') return "0";
            int len1 = chars1.length, len2 = chars2.length;
            int[] resArr = new int[len1 + len2];

            for (int i = len1 - 1; i >= 0; i--) {
                int x = chars1[i] - '0';
                for (int j = len2 - 1; j >= 0; j--) {
                    int y = chars2[j] - '0';
                    resArr[i + j + 1] += x * y;
                }
            }

            // 将各位的进位加到当前位的前一位
            for (int i = len1 + len2 - 1; i > 0; i--) {
                resArr[i - 1] += resArr[i] / 10;
                resArr[i] %= 10;
            }

            // 将数组 resArr 转成字符串，如果最高位是 0 则舍弃最高位
            StringBuilder sb = new StringBuilder();
            if (resArr[0] != 0) {
                sb.append(resArr[0]);
            }
            for (int i = 1; i < resArr.length; i++) {
                sb.append(resArr[i]);
            }

            return sb.toString();
        }

        /**
         * 模拟数学乘法过程
         * @param num1
         * @param num2
         * @return
         */
        public String multiply1(String num1, String num2) {
            char[] chars1 = num1.toCharArray();
            char[] chars2 = num2.toCharArray();
            if (chars1[0] == '0' || chars2[0] == '0') return "0";
            StringBuilder res = new StringBuilder();
            res.append('0');
            StringBuilder preRes = res;

            if (chars1.length >= chars2.length) {
                for (int i = chars2.length - 1; i >= 0; i--) {
                    StringBuilder singleLine = new StringBuilder();
                    int carry = 0;
                    int n2 = chars2[i] - '0';

                    for (int j = chars1.length - 1; j >= 0; j--) {
                        int n1 = chars1[j] - '0';
                        singleLine.append((n1 * n2 + carry) % 10);
                        carry = (n1 * n2 + carry) / 10;
                    }
                    if (carry != 0) singleLine.append(carry);
                    singleLine = singleLine.reverse();
                    for (int j = 0; j < chars2.length - i - 1; j++) {
                        singleLine.append('0');
                    }


                    System.out.println(singleLine.toString());

                    res = new StringBuilder();
                    carry = 0;
                    for (int j = singleLine.length() - 1; j >= 0; j--) {
                        int tmp1 = singleLine.charAt(j) - '0';
                        int sub = singleLine.length() - preRes.length();
                        int tmp2 = j - sub >= 0 ? preRes.charAt(j - sub) - '0' : 0;

                        res.append((tmp1 + tmp2 + carry) % 10);
                        carry = (tmp1 + tmp2 + carry) / 10;
                    }

                    if (carry != 0) res.append(carry);

                    preRes = res.reverse();
                }


                return res.toString();
            } else {
                return multiply1(num2, num1);
            }
        }

        public String multiply(String num1, String num2) {
            return multiply2(num1, num2);
        }
    }

}
